<!DOCTYPE HTML>
<html lang="zh-CN" class="sidebar-visible no-js light">
    <head>
        <!-- Book generated using mdBook -->
        <meta charset="UTF-8">
        <title> KeyPoints - PurpleDragonBookAnswer</title>


        <!-- Custom HTML head -->
        
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="Purple Dragon Book Answer Online Edition">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff" />

        <link rel="icon" href="../../favicon.svg">
        <link rel="shortcut icon" href="../../favicon.png">
        <link rel="stylesheet" href="../../css/variables.css">
        <link rel="stylesheet" href="../../css/general.css">
        <link rel="stylesheet" href="../../css/chrome.css">
        <link rel="stylesheet" href="../../css/print.css" media="print">

        <!-- Fonts -->
        <link rel="stylesheet" href="../../FontAwesome/css/font-awesome.css">
        <link rel="stylesheet" href="../../fonts/fonts.css">

        <!-- Highlight.js Stylesheets -->
        <link rel="stylesheet" href="../../highlight.css">
        <link rel="stylesheet" href="../../tomorrow-night.css">
        <link rel="stylesheet" href="../../ayu-highlight.css">

        <!-- Custom theme stylesheets -->

    </head>
    <body>
        <!-- Provide site root to javascript -->
        <script type="text/javascript">
            var path_to_root = "../../";
            var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
        </script>

        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script type="text/javascript">
            try {
                var theme = localStorage.getItem('mdbook-theme');
                var sidebar = localStorage.getItem('mdbook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script type="text/javascript">
            var theme;
            try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
            if (theme === null || theme === undefined) { theme = default_theme; }
            var html = document.querySelector('html');
            html.classList.remove('no-js')
            html.classList.remove('light')
            html.classList.add(theme);
            html.classList.add('js');
        </script>

        <!-- Hide / unhide sidebar before it is displayed -->
        <script type="text/javascript">
            var html = document.querySelector('html');
            var sidebar = 'hidden';
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            }
            html.classList.remove('sidebar-visible');
            html.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <div class="sidebar-scrollbox">
                <ol class="chapter"><li class="chapter-item expanded "><a href="../../preface.html"><strong aria-hidden="true">1.</strong> Preface</a></li><li class="chapter-item expanded "><a href="../../ch01/ch01.html"><strong aria-hidden="true">2.</strong> Chapter 1</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch01/1.1/1.1.html"><strong aria-hidden="true">2.1.</strong> Section 1.1</a></li><li class="chapter-item expanded "><a href="../../ch01/1.3/1.3.html"><strong aria-hidden="true">2.2.</strong> Section 1.3</a></li><li class="chapter-item expanded "><a href="../../ch01/1.6/1.6.html"><strong aria-hidden="true">2.3.</strong> Section 1.6</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch02/ch02.html"><strong aria-hidden="true">3.</strong> Chapter 2</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch02/key-point/key-point.html" class="active"><strong aria-hidden="true">3.1.</strong> KeyPoints</a></li><li class="chapter-item expanded "><a href="../../ch02/2.2/2.2.html"><strong aria-hidden="true">3.2.</strong> Section 2.2</a></li><li class="chapter-item expanded "><a href="../../ch02/2.3/2.3.html"><strong aria-hidden="true">3.3.</strong> Section 2.3</a></li><li class="chapter-item expanded "><a href="../../ch02/2.4/2.4.html"><strong aria-hidden="true">3.4.</strong> Section 2.4</a></li><li class="chapter-item expanded "><a href="../../ch02/2.6/2.6.html"><strong aria-hidden="true">3.5.</strong> Section 2.6</a></li><li class="chapter-item expanded "><a href="../../ch02/2.8/2.8.html"><strong aria-hidden="true">3.6.</strong> Section 2.8</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch03/ch03.html"><strong aria-hidden="true">4.</strong> Chapter 3</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch03/key-point/key-point.html"><strong aria-hidden="true">4.1.</strong> KeyPoints</a></li><li class="chapter-item expanded "><a href="../../ch03/3.1/3.1.html"><strong aria-hidden="true">4.2.</strong> Section 3.1</a></li><li class="chapter-item expanded "><a href="../../ch03/3.3/3.3.html"><strong aria-hidden="true">4.3.</strong> Section 3.3</a></li><li class="chapter-item expanded "><a href="../../ch03/3.4/3.4.html"><strong aria-hidden="true">4.4.</strong> Section 3.4</a></li><li class="chapter-item expanded "><a href="../../ch03/3.5/3.5.html"><strong aria-hidden="true">4.5.</strong> Section 3.5</a></li><li class="chapter-item expanded "><a href="../../ch03/3.6/3.6.html"><strong aria-hidden="true">4.6.</strong> Section 3.6</a></li><li class="chapter-item expanded "><a href="../../ch03/3.7/3.7.html"><strong aria-hidden="true">4.7.</strong> Section 3.7</a></li><li class="chapter-item expanded "><a href="../../ch03/3.8/3.8.html"><strong aria-hidden="true">4.8.</strong> Section 3.8</a></li><li class="chapter-item expanded "><a href="../../ch03/3.9/3.9.html"><strong aria-hidden="true">4.9.</strong> Section 3.9</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch04/ch04.html"><strong aria-hidden="true">5.</strong> Chapter 4</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch04/key-point/key-point.html"><strong aria-hidden="true">5.1.</strong> KeyPoints</a></li><li class="chapter-item expanded "><a href="../../ch04/4.2/4.2.html"><strong aria-hidden="true">5.2.</strong> Section 4.2</a></li><li class="chapter-item expanded "><a href="../../ch04/4.3/4.3.html"><strong aria-hidden="true">5.3.</strong> Section 4.3</a></li><li class="chapter-item expanded "><a href="../../ch04/4.4/4.4.html"><strong aria-hidden="true">5.4.</strong> Section 4.4</a></li><li class="chapter-item expanded "><a href="../../ch04/4.5/4.5.html"><strong aria-hidden="true">5.5.</strong> Section 4.5</a></li><li class="chapter-item expanded "><a href="../../ch04/4.6/4.6.html"><strong aria-hidden="true">5.6.</strong> Section 4.6</a></li><li class="chapter-item expanded "><a href="../../ch04/4.7/4.7.html"><strong aria-hidden="true">5.7.</strong> Section 4.7</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch05/ch05.html"><strong aria-hidden="true">6.</strong> Chapter 5</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch05/5.1/5.1.html"><strong aria-hidden="true">6.1.</strong> Section 5.1</a></li><li class="chapter-item expanded "><a href="../../ch05/5.2/5.2.html"><strong aria-hidden="true">6.2.</strong> Section 5.2</a></li><li class="chapter-item expanded "><a href="../../ch05/5.3/5.3.html"><strong aria-hidden="true">6.3.</strong> Section 5.3</a></li><li class="chapter-item expanded "><a href="../../ch05/5.4/5.4.html"><strong aria-hidden="true">6.4.</strong> Section 5.4</a></li><li class="chapter-item expanded "><a href="../../ch05/5.5/5.5.html"><strong aria-hidden="true">6.5.</strong> Section 5.5</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch06/ch06.html"><strong aria-hidden="true">7.</strong> Chapter 6</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch06/6.1/6.1.html"><strong aria-hidden="true">7.1.</strong> Section 6.1</a></li><li class="chapter-item expanded "><a href="../../ch06/6.2/6.2.html"><strong aria-hidden="true">7.2.</strong> Section 6.2</a></li><li class="chapter-item expanded "><a href="../../ch06/6.3/6.3.html"><strong aria-hidden="true">7.3.</strong> Section 6.3</a></li><li class="chapter-item expanded "><a href="../../ch06/6.4/6.4.html"><strong aria-hidden="true">7.4.</strong> Section 6.4</a></li><li class="chapter-item expanded "><a href="../../ch06/6.5/6.5.html"><strong aria-hidden="true">7.5.</strong> Section 6.5</a></li><li class="chapter-item expanded "><a href="../../ch06/6.6/6.6.html"><strong aria-hidden="true">7.6.</strong> Section 6.6</a></li><li class="chapter-item expanded "><a href="../../ch06/6.7/6.7.html"><strong aria-hidden="true">7.7.</strong> Section 6.7</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch07/ch07.html"><strong aria-hidden="true">8.</strong> Chapter 7</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch07/7.2/7.2.html"><strong aria-hidden="true">8.1.</strong> Section 7.2</a></li><li class="chapter-item expanded "><a href="../../ch07/7.3/7.3.html"><strong aria-hidden="true">8.2.</strong> Section 7.3</a></li><li class="chapter-item expanded "><a href="../../ch07/7.3/7.4.html"><strong aria-hidden="true">8.3.</strong> Section 7.4</a></li><li class="chapter-item expanded "><a href="../../ch07/7.5/7.5.html"><strong aria-hidden="true">8.4.</strong> Section 7.5</a></li><li class="chapter-item expanded "><a href="../../ch07/7.6/7.6.html"><strong aria-hidden="true">8.5.</strong> Section 7.6</a></li><li class="chapter-item expanded "><a href="../../ch07/7.7/7.7.html"><strong aria-hidden="true">8.6.</strong> Section 7.7</a></li></ol></li><li class="chapter-item expanded "><a href="../../ch08/ch08.html"><strong aria-hidden="true">9.</strong> Chapter 8</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../ch08/8.2/8.2.html"><strong aria-hidden="true">9.1.</strong> Section 8.2</a></li><li class="chapter-item expanded "><a href="../../ch08/8.3/8.3.html"><strong aria-hidden="true">9.2.</strong> Section 8.3</a></li><li class="chapter-item expanded "><a href="../../ch08/8.4/8.4.html"><strong aria-hidden="true">9.3.</strong> Section 8.4</a></li><li class="chapter-item expanded "><a href="../../ch08/8.5/8.5.html"><strong aria-hidden="true">9.4.</strong> Section 8.5</a></li></ol></li></ol>
            </div>
            <div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
        </nav>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                                <div id="menu-bar-hover-placeholder"></div>
                <div id="menu-bar" class="menu-bar sticky bordered">
                    <div class="left-buttons">
                        <button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                            <i class="fa fa-bars"></i>
                        </button>
                        <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                            <i class="fa fa-paint-brush"></i>
                        </button>
                        <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                            <li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                        </ul>
                        <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
                            <i class="fa fa-search"></i>
                        </button>
                    </div>

                    <h1 class="menu-title">PurpleDragonBookAnswer</h1>

                    <div class="right-buttons">
                        <a href="../../print.html" title="Print this book" aria-label="Print this book">
                            <i id="print-button" class="fa fa-print"></i>
                        </a>

                    </div>
                </div>

                <div id="search-wrapper" class="hidden">
                    <form id="searchbar-outer" class="searchbar-outer">
                        <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                    </form>
                    <div id="searchresults-outer" class="searchresults-outer hidden">
                        <div id="searchresults-header" class="searchresults-header"></div>
                        <ul id="searchresults">
                        </ul>
                    </div>
                </div>

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script type="text/javascript">
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <main>
                        <h1 id="第2章要点"><a class="header" href="#第2章要点">第2章要点</a></h1>
<h3 id="1-文法语法制导翻译方案语法制导的翻译器"><a class="header" href="#1-文法语法制导翻译方案语法制导的翻译器">1. 文法、语法制导翻译方案、语法制导的翻译器</a></h3>
<p>以一个仅支持个位数加减法的表达式为例</p>
<ol>
<li>
<p>文法</p>
<p>list -&gt; list + digit | list - digit | digit</p>
<p>digit -&gt; 0 | 1 | … | 9</p>
</li>
<li>
<p>（消除了左递归的）语法制导翻译方案</p>
<p>expr -&gt; term rest</p>
<p>rest -&gt; + term { print('+') } rest | - term { print('+') } rest | ε</p>
<p>term -&gt; 0 { print('0') } | 1 { print('1') } | … | 9 { print('9') }</p>
</li>
<li>
<p>语法制导的翻译器</p>
<p>java代码见 p46</p>
</li>
</ol>
<h3 id="2-语法树语法分析树"><a class="header" href="#2-语法树语法分析树">2. 语法树、语法分析树</a></h3>
<p>以 2 + 5 - 9 为例</p>
<p><img src="./assets/dragonbook-keypoint-2.2-2.png" alt="语法树和语法分析树" /></p>
<h3 id="3-正则文法上下文无关文法上下文相关文法"><a class="header" href="#3-正则文法上下文无关文法上下文相关文法">3. 正则文法、上下文无关文法、上下文相关文法?</a></h3>
<p>文法缩写：</p>
<ul>
<li>RG：<a href="http://en.wikipedia.org/wiki/Regular_grammar">正则文法</a></li>
<li>CFG：<a href="http://en.wikipedia.org/wiki/Context-free_grammar">上下文无关文法</a></li>
<li>CSG：<a href="http://en.wikipedia.org/wiki/Context-sensitive_grammar">上下文相关文法</a></li>
</ul>
<h4 id="正则文法"><a class="header" href="#正则文法">正则文法</a></h4>
<p><a href="http://en.wikipedia.org/wiki/Regular_grammar">wiki</a></p>
<p>正则文法在标准之后所有产生式都应该满足下面三种情形中的一种：</p>
<pre><code>B -&gt; a
B -&gt; a C
B -&gt; epsilon
</code></pre>
<p>关键点在于：</p>
<ol>
<li>产生式的左手边必须是一个非终结符。</li>
<li>产生式的右手边可以什么都没有，可以有一个终结符，也可以有一个终结符加一个非终结符。</li>
</ol>
<p>从产生式的角度看，这样的规定使得每应用一条产生规则，就可以产生出零或一个终结符，直到最后产生出我们要的那个字符串。</p>
<p>从匹配的角度看，这样的规定使得每应用一条规则，就可以消耗掉一个非终结符，直到整个字符串被匹配掉。</p>
<p>这样定义的语言所对应的自动机有一种性质：有限状态自动机。</p>
<p>简单来说就是只需要记录当前的一个状态，和得到下一个输入符号，就可以决定接下来的状态迁移。</p>
<h4 id="正则文法和上下文无关文法"><a class="header" href="#正则文法和上下文无关文法">正则文法和上下文无关文法</a></h4>
<p>CFG 跟 RG 最大的区别就是，产生式的右手边可以有零或多个终结符或非终结符，顺序和个数都没限制。</p>
<p>想像一个经典例子，括号的配对匹配：</p>
<p>expr -&gt; '(' expr ')' | epsilon</p>
<p>这个产生式里（先只看第一个子产生式），右手边有一个非终结符 expr，但它的左右两侧都有终结符，这种产生式无法被标准化为严格的 RG 。这就是CFG的一个例子。</p>
<p>它对应的自动机就不只要记录当前的一个状态，还得外加记录到达当前位置的历史，才可以根据下一个输入符号决定状态迁移。所谓的“历史”在这里就是存着已匹配规则的栈。</p>
<p>CFG 对应的自动机为 PDA(下推自动机)。</p>
<p>RG 的规定严格，对应的好处是它对应的自动机非常简单，所以可以用非常高效且简单的方式来实现。</p>
<h4 id="上下文相关文法"><a class="header" href="#上下文相关文法">上下文相关文法</a></h4>
<p>CSG 在 CFG的基础上进一步放宽限制。</p>
<p>产生式的左手边也可以有终结符和非终结符。左手边的终结符就是“上下文”的来源。也就是说匹配的时候不能光看当前匹配到哪里了，还得看当前位置的左右到底有啥（也就是上下文是啥），上下文在这条规则应用的时候并不会被消耗掉，只是“看看”。</p>
<p>CSG 的再上一层是 PSG，phrase structure grammar。</p>
<p>基本上就是CSG的限制全部取消掉。</p>
<p>左右两边都可以有任意多个、任意顺序的终结符和非终结符。</p>
<p>反正不做自然语言处理的话也不会遇到这种文法，所以具体就不说了。</p>
<h3 id="4-为什么有-n-个运算符的优先级就对应-n1-个产生式"><a class="header" href="#4-为什么有-n-个运算符的优先级就对应-n1-个产生式">4. 为什么有 n 个运算符的优先级，就对应 n+1 个产生式？</a></h3>
<p>优先级的处理可以在纯文法层面解决，也可以在parser实现中用别的办法处理掉。</p>
<p>纯文法层面书上介绍的，有多少个优先级就有那么多加1个产生式。</p>
<p>书上介绍的四则运算的文法，会使得加减法离根比较近，乘除法离根比较远。</p>
<p>语法树的形状决定了节点的计算顺序，离根远的节点就会先处理，这样看起来就是乘除法先计算，也就是乘除法的优先级更高。</p>
<p>参考：http://rednaxelafx.iteye.com/blog/492667</p>
<h3 id="5-避免二义性文法的有效原则"><a class="header" href="#5-避免二义性文法的有效原则">5. 避免二义性文法的有效原则？</a></h3>
<p>二义性问题主要是跟 CFG 的特性有关系的。</p>
<p>CFG 的选择结构（&quot;|&quot;）是没有规定顺序或者说优先级的，
同时，多个规则可能会有共同前缀，
这样才会有二义性问题。</p>
<p>PEG 是跟CFG类似的一种东西，语言的表达力上跟CFG相似。
但文法层面没有二义性，因为它的选择结构（&quot;|&quot;）是有顺序或者说有优先级的。</p>
<h3 id="6-避免预测分析器因左递归文法造成的无限循环"><a class="header" href="#6-避免预测分析器因左递归文法造成的无限循环">6. 避免预测分析器因左递归文法造成的无限循环</a></h3>
<p>产生式：</p>
<p>A -&gt; A x | y</p>
<p>语法制导翻译伪代码片段：</p>
<pre><code>void A(){
    switch(lookahead){
        case x:
            A();match(x);break;
        case y:
            match(y):break;
        default:
            report(&quot;syntax error&quot;)
    }
}
</code></pre>
<p>当语句符合 A x 形式时， A() 运算会陷入死循环，可以通过将产生式改为等价的非左递归形式来避免: </p>
<p>B -&gt; y C</p>
<p>C -&gt; x C | ε</p>
<h3 id="7-为什么在右递归的文法中包含了左结合运算符的表达式翻译会比较困难"><a class="header" href="#7-为什么在右递归的文法中包含了左结合运算符的表达式翻译会比较困难">7. 为什么在右递归的文法中，包含了左结合运算符的表达式翻译会比较困难？</a></h3>
<h3 id="8-中间代码生成时的左值和右值问题"><a class="header" href="#8-中间代码生成时的左值和右值问题">8. 中间代码生成时的左值和右值问题。</a></h3>
<p>看了书上 lvalue() 和 rvalue() 的伪代码，感觉可以做左值也可以做右值的都由 lvalue() 处理，而对于右值的处理，要么自己处理掉了，对于可以作为左值的右值则调用 lvalue()。</p>
<p>为什么不直接弄个 value() 就结了？</p>

                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->
                            <a rel="prev" href="../../ch02/ch02.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                <i class="fa fa-angle-left"></i>
                            </a>

                            <a rel="next" href="../../ch02/2.2/2.2.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                <i class="fa fa-angle-right"></i>
                            </a>

                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">
                    <a rel="prev" href="../../ch02/ch02.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                        <i class="fa fa-angle-left"></i>
                    </a>

                    <a rel="next" href="../../ch02/2.2/2.2.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                        <i class="fa fa-angle-right"></i>
                    </a>
            </nav>

        </div>




        <script type="text/javascript">
            window.playground_copyable = true;
        </script>


        <script src="../../elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../mark.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../searcher.js" type="text/javascript" charset="utf-8"></script>

        <script src="../../clipboard.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../highlight.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../book.js" type="text/javascript" charset="utf-8"></script>

        <!-- Custom JS scripts -->


    </body>
</html>
